{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Continuous Subarray Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkSubarraySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连续的子数组和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子数组大小 <strong>至少为 2</strong> ，且</li>\n",
    "\t<li>子数组元素总和为 <code>k</code> 的倍数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果存在，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>如果存在一个整数 <code>n</code> ，令整数 <code>x</code> 符合 <code>x = n * k</code> ，则称 <code>x</code> 是 <code>k</code> 的一个倍数。<code>0</code> 始终视为 <code>k</code> 的一个倍数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [23<u>,2,4</u>,6,7], k = 6\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>[2,4] 是一个大小为 2 的子数组，并且和为 6 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [<u>23,2,6,4,7</u>], k = 6\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 \n",
    "42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [23,2,6,4,7], k = 13\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= nums[i] <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 <= sum(nums[i]) <= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>1 <= k <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [continuous-subarray-sum](https://leetcode.cn/problems/continuous-subarray-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [continuous-subarray-sum](https://leetcode.cn/problems/continuous-subarray-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[23,2,4,6,7]\\n6', '[23,2,6,4,7]\\n6', '[23,2,6,4,7]\\n13']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "\n",
    "        accum_sum = nums[0]\n",
    "        rec_set = set([0])\n",
    "        pre_remainder = nums[0] % k\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            accum_sum += nums[i]\n",
    "            remainder = accum_sum % k\n",
    "            if remainder in rec_set:\n",
    "                return True\n",
    "            else:\n",
    "                rec_set.add(pre_remainder)\n",
    "                pre_remainder = remainder\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        s = set()\n",
    "        pre = 0\n",
    "        for i in nums:\n",
    "            last = pre\n",
    "            pre+=i\n",
    "            pre%=k\n",
    "\n",
    "            if pre in s:\n",
    "                return True\n",
    "        \n",
    "\n",
    "            s.add(last)\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        hash_set= set()\n",
    "        s = 0\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            if s % k in hash_set:\n",
    "                return True\n",
    "            hash_set.add((s-i) % k)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        mode=set()\n",
    "        presum=0\n",
    "        for num in nums:\n",
    "            last=presum\n",
    "            presum+=num\n",
    "            presum%=k\n",
    "            if presum in mode:\n",
    "                return True\n",
    "            mode.add(last)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        mem = set()\n",
    "        sums = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            sums[i + 1] = sums[i] + nums[i]\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            mem.add(sums[i - 2] % k)\n",
    "            if sums[i] % k in mem:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        d = set([0])\n",
    "        num = nums[0]%k\n",
    "        for i in nums[1:]:\n",
    "            if (num + i)%k in d:\n",
    "                return True\n",
    "            d.add(num)\n",
    "            num += i\n",
    "            num %= k\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        prefix = [0] * (len(nums) + 1)\n",
    "        s = set()\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            prefix[i + 1] = prefix[i] + nums[i]\n",
    "            if i == 0:\n",
    "                continue\n",
    "            s.add(prefix[i-1])\n",
    "            if i < (prefix[i + 1] + 1) // k:\n",
    "                for j in reversed(range(0, i)):\n",
    "                    if (prefix[i + 1] - prefix[j]) % k == 0:\n",
    "                        return True\n",
    "            else:\n",
    "                for j in range(0, prefix[i + 1] + 1, k):\n",
    "                    if prefix[i + 1] - j in s: \n",
    "                        return True\n",
    "\n",
    "            # for j in range(0, prefix[i + 1] + 1, k):\n",
    "            #         if prefix[i + 1] - j in s: \n",
    "            #             return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        prefix = [0] * len(nums)\n",
    "        prefix[0] = nums[0] % k\n",
    "        visited = set()\n",
    "        for i in range(1, len(nums)):\n",
    "            prefix[i] = (prefix[i-1] + nums[i]) % k\n",
    "            if prefix[i] in visited or i >= 1 and prefix[i] == 0:\n",
    "                return True\n",
    "            visited.add(prefix[i-1])          \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        check_set = {0}\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i-1]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] % k in check_set:\n",
    "                return True\n",
    "            check_set.add(nums[i-1] % k)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        p = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            p[i] = p[i - 1] + nums[i - 1]\n",
    "        \n",
    "        s = set([0])\n",
    "        for i in range(2, n + 1):\n",
    "            a = p[i] % k\n",
    "            if a in s:\n",
    "                return True\n",
    "            s.add(p[i - 1] % k)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        pre_sum =  [0] * (len(nums)+1)\n",
    "        for i in range(1,len(nums)+1):\n",
    "            pre_sum[i] = pre_sum[i-1] + nums[i-1]\n",
    "        set_data = set()\n",
    "        for i in range(2,len(nums)+1):\n",
    "            set_data.add(pre_sum[i-2]%k)\n",
    "            if pre_sum[i] % k in set_data:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        maxdif=0\n",
    "        prefix=[nums[0]%k]\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return False\n",
    "\n",
    "        for num in nums[1:]:\n",
    "            prefix.append((num%k+prefix[-1])%k)\n",
    "\n",
    "        ele=set([0])\n",
    "        #长度为二，那就放i-2\n",
    "        i=1\n",
    "        while i<n:\n",
    "            if prefix[i] in ele:\n",
    "                return True\n",
    "            ele.add(prefix[i-1])\n",
    "            i+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        l = [i%k for i in itertools.accumulate([0]+nums)]\n",
    "        s = {l[0]}\n",
    "        for i in range(2, len(l)):\n",
    "            if l[i] in s: return True\n",
    "            s.add(l[i-1])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        preSum = [nums[0] % k]\n",
    "        for num in nums[1:]:\n",
    "            preSum.append((preSum[-1] + num) % k)\n",
    "        \n",
    "        print(preSum)\n",
    "        st = set()\n",
    "        st.add(0)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if preSum[i] in st:\n",
    "                return True\n",
    "            st.add(preSum[i-1])\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        prefix = [0] * len(nums)\n",
    "        prefix[0] = nums[0] % k\n",
    "        for i in range(1, len(nums)):\n",
    "            prefix[i] = (prefix[i-1] + nums[i]) % k\n",
    "        print(prefix)\n",
    "        visited = set()\n",
    "        for i in range(1, len(prefix)):\n",
    "            if prefix[i] % k in visited:\n",
    "                return True\n",
    "            if i >= 1 and prefix[i] == 0:\n",
    "                return True\n",
    "            visited.add(prefix[i-1] % k)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        presum=Counter()\n",
    "        count=0\n",
    "        for i in range(len(nums)):\n",
    "            count=(count+nums[i])%k\n",
    "            if i==0:\n",
    "                continue\n",
    "            presum[count]+=1\n",
    "        sumnum=nums[0]%k\n",
    "        count=0\n",
    "        target=0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if target in presum:\n",
    "                return True\n",
    "            sumnum=(sumnum+nums[i])%k\n",
    "            target=(target+nums[i-1])%k\n",
    "            presum[sumnum]-=1\n",
    "            if presum[sumnum]==0:\n",
    "                presum.pop(sumnum)\n",
    "        if target in presum:\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        dic ={0:1}\n",
    "        total = 0\n",
    "        res = 0 \n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % k == 0 and i + 1 <= len(nums) - 1 and nums[i + 1] % k != 0:\n",
    "                continue\n",
    "            if nums[i] % k == 0 and i - 1 >=0 and  nums[i - 1] % k != 0 :\n",
    "                continue\n",
    "            total = (total +  nums[i]) % k\n",
    "            res += dic.get(total,0)\n",
    "            dic[total] = dic.get(total,0) + 1\n",
    "        \n",
    "        if res == 0:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        dic = {0: -1}\n",
    "        presum = 0\n",
    "        for index, num in enumerate(nums):\n",
    "            presum += num\n",
    "            rem = presum % k\n",
    "            i = dic.get(rem, index)\n",
    "            if i == index:\n",
    "                dic[rem] = index\n",
    "            elif index - i >= 2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        visit = defaultdict(bool)\n",
    "        preSum = nums[0]\n",
    "        prepreSum = 0\n",
    "        visit[0] = True\n",
    "        for num in nums[1:]:\n",
    "            prepreSum = preSum\n",
    "            preSum += num\n",
    "            if visit[preSum % k]:\n",
    "                return True\n",
    "            visit[prepreSum % k] = True\n",
    "        return False\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        ls=[0 for i in range(n)]\n",
    "        dict1={0:1}\n",
    "        r=0\n",
    "        for i in range(1,n):\n",
    "            if i==1:\n",
    "                ls[i]=0\n",
    "            else:\n",
    "                ls[i]=(ls[i-1]+nums[i-2])%k\n",
    "            xi=(ls[i]+nums[i-1]+nums[i])%k\n",
    "\n",
    "            if ls[i] not in dict1.keys():\n",
    "                dict1.update({ls[i]:1})\n",
    "            elif ls[i] in dict1.keys():\n",
    "                dict1[ls[i]]+=1\n",
    "            if xi in dict1.keys():\n",
    "                r+=dict1[xi]\n",
    "        if r>0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False\n",
    "        if n == 2:\n",
    "            return sum(nums)%k == 0\n",
    "        pre = [0]*(n+1)\n",
    "        count = {}\n",
    "        count[0] = 1\n",
    "        pre[1] = nums[0]\n",
    "        min_value = 0\n",
    "        # ans = 0\n",
    "        for i in range(1, n):\n",
    "            # 求前缀和\n",
    "            pre[i+1] = pre[i] + nums[i]\n",
    "            # 对每个前缀和，先查看之前的数是否满足pre[j] = pre[i+1] - j*k\n",
    "            j = 0\n",
    "            while pre[i+1] - j*k >= min_value:\n",
    "                if pre[i+1] - j*k in count:\n",
    "                    return True\n",
    "                    # ans += count[pre[i+1] - j*k]\n",
    "                j = j + 1\n",
    "            # 再记录前一个数（注意不能先记录再查看）\n",
    "            if pre[i] not in count:\n",
    "                count[pre[i]] = 1\n",
    "            # else:\n",
    "            #     count[pre[i]] += 1\n",
    "            min_value = min(min_value, pre[i])\n",
    "        return False\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "        hash_new = defaultdict(int)\n",
    "        li_stack= []\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)):\n",
    "            cnt += nums[i]\n",
    "            li_stack.append(cnt)\n",
    "        for i in range(1,len(li_stack)):\n",
    "            if(i >= 2):\n",
    "                hash_new[li_stack[i-2]%k] += 1\n",
    "            \n",
    "            tmp = li_stack[i] % k\n",
    "            if(tmp == 0):\n",
    "                return True\n",
    "            elif(hash_new[tmp]):\n",
    "                return True\n",
    "\n",
    "            # for j in range(i):\n",
    "            #     # print(li_stack[i] - li_stack[j])\n",
    "            #     if((li_stack[i] - li_stack[j] + nums[j])%k == 0):\n",
    "            #         return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        # 简单前缀和而已\n",
    "        pre = accumulate(nums, initial=0)\n",
    "        pre = [x % k for x in pre]\n",
    "        m = defaultdict(int)\n",
    "        for i, x in enumerate(pre):\n",
    "            if i - 2 >= 0:\n",
    "                m[pre[i-2]] += 1\n",
    "            if m[x]: return True\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    题目：给定整数数组nums和一个整数k。判断是否存在长度>=2且元素和能被k整除的连续子数组，返回True/False.\n",
    "    关键：前缀和哈希表的value=i,pre[i]=i\n",
    "    '''\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        length = len(nums)\n",
    "        # if length < 2:\n",
    "        #     return False\n",
    "        pre_sum = 0\n",
    "        pre_div_count_map = dict()\n",
    "        #前缀和哈希表首个元素的初始化：合理且必要\n",
    "        #能且只能初始化pre[0]=-1\n",
    "        pre_div_count_map[0] = -1\n",
    "        for i in range(length):\n",
    "            pre_sum += nums[i]\n",
    "            cur_remainder = pre_sum % k\n",
    "            if cur_remainder in pre_div_count_map:\n",
    "                if (i-pre_div_count_map[cur_remainder] > 1):\n",
    "                    return True\n",
    "            else:\n",
    "                pre_div_count_map[cur_remainder] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        s1, s2 = 0, nums[0]\n",
    "        d = Counter()\n",
    "        d[0] = 1\n",
    "        for l, r in zip(nums[:-1], nums[1:]):\n",
    "            s1 += l\n",
    "            s2 += r\n",
    "            if d[s2 % k] > 0:\n",
    "                return True\n",
    "            d[s1 % k] += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        first = {0:-1}\n",
    "        s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s = (s+x)%k\n",
    "            j = first.get(s,-2)\n",
    "            if j ==-2:\n",
    "                first[s] = i\n",
    "            elif i-j >= 2:\n",
    "                return True\n",
    "            # print(first)\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        nums[0] %= k\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            nums[i] = (nums[i] + nums[i-1])%k\n",
    "            \n",
    "        pres = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            target = nums[i]\n",
    "\n",
    "            if target == 0 and i >= 1:\n",
    "                return True\n",
    "            \n",
    "            if target in pres and i - pres[target] >= 2:\n",
    "                return True\n",
    "            \n",
    "            if nums[i] not in pres:\n",
    "                pres[nums[i]] = i\n",
    "    \n",
    "\n",
    "        return False\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        t=[0 for i in range(n)]\n",
    "        d={0:-1}\n",
    "        for i in range(n):\n",
    "            t[i]=(t[i-1]+nums[i])%k\n",
    "            if t[i] not in d:\n",
    "                d[t[i]]=i\n",
    "            else:\n",
    "                if d[t[i]]<i-1:\n",
    "                    # print(t)\n",
    "                    return True\n",
    "        # print(t)\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "#         n = len(nums)\n",
    "#         pre = [0] * n\n",
    "#         pre[0] = nums[0]\n",
    "#         for i in range(1, n):\n",
    "#             pre[i] = pre[i-1] + nums[i]\n",
    "#         for i in range(n-1):\n",
    "#             for j in range(i+1, n):\n",
    "#                 # print(i, j, pre)\n",
    "#                 if i == 0:\n",
    "#                     if pre[j] % k == 0:\n",
    "#                         return True\n",
    "#                 if (pre[j]-pre[i]) % k == 0:\n",
    "#                     if j - i > 1:\n",
    "#                         return True\n",
    "#         return False\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i-1] + nums[i]\n",
    "        dic = { 0: -1 }\n",
    "        for i in range(n):\n",
    "            s = pre[i] % k\n",
    "            if s in dic:\n",
    "                if i - dic[s] > 1:\n",
    "                    return True\n",
    "            else:\n",
    "                dic[s] = i\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        mod_dict = {0: -1}\n",
    "        sum_mod = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum_mod = (nums[i] + sum_mod) % k\n",
    "            if sum_mod in mod_dict and i - mod_dict[sum_mod] > 1:               \n",
    "                return True\n",
    "            if sum_mod not in mod_dict:\n",
    "                mod_dict[sum_mod] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Prefix sum + hashmap. Time O(n) Space O(n)\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        prefix = {0: 0}\n",
    "        curSum = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            remainder = curSum % k\n",
    "            if remainder in prefix.keys():\n",
    "                if i + 1 - prefix[remainder] >= 2:\n",
    "                    return True\n",
    "            else:\n",
    "                prefix[remainder] = i + 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        prefix = {0: 0}\n",
    "        curSum = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            remainder = curSum % k\n",
    "            if remainder in prefix.keys():\n",
    "                if i + 1 - prefix[remainder] >= 2:\n",
    "                    return True\n",
    "            else:\n",
    "                prefix[remainder] = i + 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        ans = 0\n",
    "        # (P[r+1] - P[l]) % k = 0\n",
    "        P = [0] + list(accumulate(nums))\n",
    "        aux = Counter([0])\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                ans += aux[(P[i+1] % k) ]\n",
    "            aux[P[i]%k] += 1\n",
    "        return ans > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        prenum=[nums[0]%k]\n",
    "        dic={}\n",
    "        dic[prenum[0]] =0\n",
    "        for i in range(1,len(nums)):\n",
    "            prenum.append((prenum[i-1]+nums[i])%k)\n",
    "            if prenum[i] in dic:\n",
    "                if i >=dic[prenum[i]]+2:\n",
    "                    return True\n",
    "            else:\n",
    "                dic[prenum[i]] = i\n",
    "            \n",
    "        if 0 in dic:\n",
    "            if dic[0] > 0:\n",
    "                return True\n",
    "\n",
    "        if len(prenum) == 2:\n",
    "            if prenum[-2] == 0:\n",
    "                return True\n",
    "\n",
    "        print(prenum)\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        prefixsum = [0] * n\n",
    "        prefixsum[0] = nums[0] % k\n",
    "        ans = False\n",
    "        st = {}\n",
    "        st[prefixsum[0]] = 0\n",
    "        for i in range(1,n):\n",
    "            prefixsum[i] = (prefixsum[i-1] + nums[i]) % k\n",
    "            if prefixsum[i] % k == 0:\n",
    "                ans = True\n",
    "                break\n",
    "            if prefixsum[i] not in st:\n",
    "                st[prefixsum[i]] = i\n",
    "            elif st[prefixsum[i]] != i-1:\n",
    "                ans = True\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<2:\n",
    "            return False\n",
    "        nums = [0] +nums[:]\n",
    "        visited = defaultdict(int)\n",
    "        cnt = 0\n",
    "        visited[0] = 0\n",
    "        for i in range(len(nums)):\n",
    "            cnt += nums[i] % k\n",
    "            cnt %= k\n",
    "            if cnt in visited:\n",
    "                if i-visited[cnt]>=2:\n",
    "                    return True\n",
    "            else:\n",
    "                visited[cnt] = i\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        # 子数组长度至少为2,且总和为k的倍数 \n",
    "        # 跟前边和能整除p有点像,但一个是找出可以整除k的子数组\n",
    "        # 一个是移除子数组后,剩下的能整除p(本题找能被整除的,另一道题是找需要移除的)\n",
    "\n",
    "        s = list(accumulate(nums,initial=0))\n",
    "        s = [i%k for i in s]\n",
    "        n = len(nums)\n",
    "        mp = defaultdict(int)\n",
    "        for i in range(n+1):\n",
    "            # 搜索 取余k = 0 的子数组是否存在 == 前缀和(求余运算构造的)数组中是否有重复元素且距离>1(需要满足长度至少=2)\n",
    "            if s[i] in mp and i-mp[s[i]]>1:\n",
    "                # 如果有重复元素且满足长度>=2\n",
    "                return True\n",
    "            if s[i] not in mp:\n",
    "                mp[s[i]] = i\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            pre.append((pre[-1]+num)%k)\n",
    "        first = {}\n",
    "\n",
    "        for i,v in enumerate(pre):\n",
    "            if first.get(v,-1)==-1:\n",
    "                first[v]=i\n",
    "            elif i-first.get(v) >1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            pre.append((pre[-1]+num)%k)\n",
    "        first = {}\n",
    "\n",
    "        for i,v in enumerate(pre):\n",
    "            if first.get(v,-1)==-1:\n",
    "                first[v]=i\n",
    "            elif i-first.get(v) >1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        size = len(nums)\n",
    "        pre_sum = [0] * (size + 1)\n",
    "        yu_dic = {}\n",
    "        for i in range(size):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "        \n",
    "        for i in range(size + 1):\n",
    "            if pre_sum[i] % k in yu_dic: \n",
    "                if i - yu_dic[pre_sum[i] % k] > 1:\n",
    "                    return True\n",
    "            else:\n",
    "                yu_dic[pre_sum[i] % k] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        pre[0] = nums[0]\n",
    "        if n < 2:\n",
    "            return False\n",
    "        for i in range(1,n):\n",
    "            pre[i] += pre[i-1] + nums[i] \n",
    "        hashmap = {0:-1}\n",
    "        for i in range(n):\n",
    "            remainder = pre[i] % k\n",
    "            if remainder not in hashmap:\n",
    "                hashmap[remainder] = i\n",
    "                #记录第一次的位置，如果用and\n",
    "            elif i - hashmap[remainder] > 1:\n",
    "                return True\n",
    "        return False\n",
    "#前缀和需要注意不能num[j]+...+num[i] = pre[i] - pre[j]\n",
    "#同余定理：如果2者与k的值的余数相等，那么他们是的和是k的n倍"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: list[int], k: int) -> bool:\n",
    "        array_dict = {0:-1}\n",
    "        array_len = 0 \n",
    "        array_sum = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            array_sum = array_sum + v\n",
    "            array_mod = array_sum % k\n",
    "            \n",
    "            if array_mod not in array_dict:\n",
    "                array_dict[array_mod] = i\n",
    "            else:\n",
    "                array_len = max(array_len, i - array_dict[array_mod])\n",
    "        print(array_dict)\n",
    "        print(array_len)      \n",
    "        if array_len >= 2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        key = 0\n",
    "        look = {0:-1}\n",
    "        presum = 0\n",
    "        for i in range(len(nums)):\n",
    "            presum += nums[i]\n",
    "            key = presum if k == 0 else presum % k\n",
    "            if key in look:\n",
    "                print(look)\n",
    "                if i - look[key] >= 2:\n",
    "                    return True\n",
    "            else:\n",
    "                look[key] = i\n",
    "        print(look)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        rem2Index = {0: -1}\n",
    "        preSums = [0]\n",
    "        for idx, num in enumerate(nums):\n",
    "            currentSum = num + preSums[-1]\n",
    "            preSums.append(currentSum)\n",
    "            if currentSum % k in rem2Index:\n",
    "                if idx - rem2Index[currentSum % k] >= 2:\n",
    "                    return True\n",
    "            else:\n",
    "                rem2Index[currentSum % k] = idx\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums, k):\n",
    "        length = len(nums)\n",
    "        start = 0\n",
    "        res = {}\n",
    "        index = 0\n",
    "\n",
    "        if length < 2:\n",
    "            return False\n",
    "\n",
    "        while start < length - 1:\n",
    "            nums[start+1] += nums[start]\n",
    "            start += 1\n",
    "\n",
    "        while index < length:\n",
    "            num = nums[index]\n",
    "            if num % k == 0 and index >= 1 or (num % k in res.keys() and res[num % k] < index - 1):\n",
    "                return True\n",
    "            else:\n",
    "                if num % k  not in res.keys():\n",
    "                    res[num % k] = index\n",
    "            index += 1\n",
    "        return False\n",
    "\n",
    "nums = [5,0,0,0]\n",
    "s = Solution()\n",
    "print(s.checkSubarraySum(nums, 3))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        pre[0] = nums[0]\n",
    "        dic = collections.defaultdict()\n",
    "        dic[pre[0] % k] = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] + nums[i]\n",
    "            if pre[i] % k == 0:\n",
    "                return True\n",
    "\n",
    "            if pre[i] % k in dic:\n",
    "                if i - dic[pre[i] % k] > 1:\n",
    "                    return True\n",
    "            else:\n",
    "                dic[pre[i] % k] = i\n",
    "        \n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        presum=[0]*(n+1)\n",
    "        di={}\n",
    "        di[0]=-1\n",
    "        ans=0\n",
    "\n",
    "        for i in range(n):\n",
    "            presum[i+1]=presum[i]+nums[i]\n",
    "\n",
    "             \n",
    "            if presum[i+1]%k in di and (i-di[presum[i+1]%k])>=2: \n",
    "                return True\n",
    "            \n",
    "            if presum[i+1]%k not in di:\n",
    "                di[presum[i+1]%k]=i\n",
    "        return False\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        length = len(nums)\n",
    "        if length < 2:\n",
    "            return False \n",
    "        pre = [0] * length\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, length):\n",
    "            pre[i] = pre[i -1] + nums[i]\n",
    "            if pre[i] % k == 0:\n",
    "                return True\n",
    "        mp = {}\n",
    "        for i in range(length):\n",
    "            re = pre[i] % k\n",
    "            if re in mp.keys():\n",
    "                j = mp[re]\n",
    "                if i - j > 1:\n",
    "                    return True\n",
    "            else:\n",
    "                mp[re] = i\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        sum, n, mp = [], len(nums), {0 : -1}\n",
    "        sum.append(nums[0])\n",
    "        for i in range(1, n) :\n",
    "            sum.append(sum[-1] + nums[i])\n",
    "        for i in range(n) :\n",
    "            if sum[i] % k in mp :\n",
    "                if i - mp[sum[i] % k] >= 2 :\n",
    "                    return True\n",
    "            else : mp[sum[i] % k] = i\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums)<2:\n",
    "            return False\n",
    "        presum=[0]\n",
    "        for i in range(len(nums)):\n",
    "            presum.append(presum[-1]+nums[i])\n",
    "        presum=presum[1:]\n",
    "        dict1={0:-1}\n",
    "        for i in range(len(presum)):\n",
    "            yu=presum[i]%k\n",
    "            if yu in dict1:\n",
    "                if i-dict1[yu]>=2:\n",
    "                    return True\n",
    "            else:\n",
    "                dict1[yu]=i\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        sub = list(map(lambda x:x%k,nums))\n",
    "        prefix = [0]*(len(sub)+1)\n",
    "        s = 0 \n",
    "        for j in range(len(sub)):\n",
    "            prefix[j+1] = sub[j] + prefix[j]\n",
    "        d = {}\n",
    "        for i in range(len(prefix)):\n",
    "            if prefix[i] % k in d and i - d[prefix[i]%k] > 1:\n",
    "                return True\n",
    "            if prefix[i] % k not in d:\n",
    "                d[prefix[i]%k] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        #前缀和+哈希表\n",
    "        #若s[r] - s[l - 1] % k == 0 且r - l > 1\n",
    "        leave = {0:0} \n",
    "        n = len(nums)\n",
    "        nums = [0] + nums\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1] + nums[i]\n",
    "            print(s[i])\n",
    "            if s[i] % k in leave and i - leave[s[i] % k] > 1:\n",
    "                return True\n",
    "            elif s[i] % k not in leave:\n",
    "                leave[s[i] % k] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) > 2 * k - 1:\n",
    "            return True\n",
    "        prefix_sum = nums[0]\n",
    "        mod_dict = dict()\n",
    "        mod_dict[prefix_sum % k] = [0]\n",
    "        for i in range(1, len(nums)):\n",
    "            prefix_sum += nums[i]\n",
    "            mod = prefix_sum % k\n",
    "            if mod == 0:\n",
    "                return True\n",
    "            if mod in mod_dict:\n",
    "                if i - mod_dict[mod][0] > 1:\n",
    "                    return True\n",
    "                mod_dict[mod].append(i)\n",
    "            else:\n",
    "                mod_dict[mod] = [i]\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        record = {0:[-1]}\n",
    "        last = 0\n",
    "        for idx,num in enumerate(nums):\n",
    "            last = (last+num)%k\n",
    "            if last not in record:\n",
    "                record[last] = [idx]\n",
    "            elif idx-record[last][0] >= 2:\n",
    "                return True\n",
    "            else:\n",
    "                record[last].append(idx)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        preSum = collections.defaultdict(int)\n",
    "        preSum[0] = 0\n",
    "        dp = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for n in range(1,len(nums)+1):\n",
    "            ans += nums[n-1]\n",
    "            preSum[n] = ans\n",
    "\n",
    "        for i in range(2,len(nums)+1):\n",
    "            dp[preSum[i-2]%k] +=1\n",
    "            if dp[preSum[i]%k] >0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        d = {0: (1, -1)}\n",
    "        preSum = 0\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            preSum += num\n",
    "            mod = preSum % k\n",
    "            same, index = d.get(mod, (0, 0))\n",
    "            if same > 0 and i - index > 1:\n",
    "                return True\n",
    "            if same == 0:\n",
    "                d[mod] = (1, i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        dic = dict()\n",
    "        prefixSum = [0] * len(nums)\n",
    "        prefixSum[0] = nums[0] % k \n",
    "        dic[prefixSum[0]] = [0]\n",
    "        for i in range(1, len(prefixSum)):\n",
    "            prefixSum[i] = (prefixSum[i-1] + nums[i]) % k\n",
    "            if prefixSum[i] == 0:\n",
    "                return True \n",
    "            if prefixSum[i] not in dic:\n",
    "                dic[prefixSum[i]] = [i]\n",
    "            else:\n",
    "                comp = dic[prefixSum[i]][0]\n",
    "                if i - comp >= 2: return True \n",
    "                else:\n",
    "                    dic[prefixSum[i]].append(i)\n",
    "        \n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        presum = [0]*(len(nums))\n",
    "        cnt = []\n",
    "        presum[0] = nums[0]%k\n",
    "\n",
    "        presum_dict = {}\n",
    "        presum_dict[presum[0]] = [0]\n",
    "\n",
    "        #prev_0 = False\n",
    "        #for i in range(len(nums)):\n",
    "        #    if nums[i] == 0 and prev_0 == True:\n",
    "        #        return True\n",
    "\n",
    "        #    if nums[i] == 0 and prev_0 == False:\n",
    "        #        prev_0 = True\n",
    "\n",
    "        #    if nums[i] != 0:\n",
    "        #        prev_0 = False\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            cur = (presum[i-1] + nums[i]) % k\n",
    "\n",
    "            if cur == 0 and i > 0:\n",
    "                return True\n",
    "            if cur in presum_dict:\n",
    "                indexes = presum_dict[cur]\n",
    "                for item in indexes:\n",
    "                    if i-item >= 2:\n",
    "                        return True\n",
    "            presum[i] = cur\n",
    "            if cur in presum_dict:\n",
    "                presum_dict[cur].append(i)\n",
    "            else:\n",
    "                presum_dict[cur] = [i]\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        nums = [num % k for num in nums]\n",
    "        acc = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            acc[i + 1] = (acc[i] + nums[i]) % k\n",
    "\n",
    "        print(acc)\n",
    "        res = 0\n",
    "        d = dict({0: 0})\n",
    "        for i in range(1, n + 1):\n",
    "            t = (k - acc[i]) % k\n",
    "            if t in d and d[t] < i - 1:\n",
    "                return True\n",
    "\n",
    "            if t not in d:\n",
    "                d[t] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        dic = dict()\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        num_sum = 0\n",
    "        dic[0] = (-1, 0)\n",
    "        for i, num in enumerate(nums):\n",
    "            num_sum += num\n",
    "            if(num_sum % k) not in dic.keys():\n",
    "                dic[num_sum % k] = (i, num_sum % k)\n",
    "            else:\n",
    "                cnt = i - dic[num_sum % k][0]\n",
    "                if cnt >= 2:\n",
    "                    return True\n",
    "        return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        prefix = dict()\n",
    "        prefix[-1] = 0\n",
    "        map = dict()\n",
    "        map[0] = -1\n",
    "        for i in range(len(nums)):\n",
    "            prefix[i] = prefix[i - 1] + nums[i]\n",
    "            if prefix[i] % k in map:\n",
    "                if i - map[prefix[i] % k] >= 2:\n",
    "                    return True\n",
    "            else:\n",
    "                map[prefix[i] % k] = i\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "        # 前缀和\n",
    "        n = len(nums)\n",
    "        presum = 0\n",
    "        record = defaultdict(list)\n",
    "        record[0] = [-1]\n",
    "        for i in range(n):\n",
    "            presum += nums[i]\n",
    "            mod = presum % k \n",
    "            if mod in record:\n",
    "                for j in record[mod]:\n",
    "                    if i-j >= 2:\n",
    "                        return True\n",
    "                # return True\n",
    "            record[mod].append(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = dict()\n",
    "        s = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num\n",
    "            if i > 0 and (s == k or s % k == 0):\n",
    "                return True\n",
    "            m = s % k\n",
    "            loc, n = cnt.get(m, (i, 0))\n",
    "            if n > 0 and i - loc > 1:\n",
    "                return True\n",
    "            loc, n = cnt.get(m, (i, 0))\n",
    "            cnt[m] = (min(loc, i), n+1)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if k == 1 and len(nums) > 1: return True\n",
    "        md = {}\n",
    "        xd = {}\n",
    "        s = 0\n",
    "        c = 0\n",
    "        md[0] = 1\n",
    "        xd[0] = 0\n",
    "        cd = [0]\n",
    "        for i in range(len(nums)):\n",
    "            # print('md:', md)\n",
    "            # print('xd:', xd)\n",
    "            # print('cd:', cd)\n",
    "            s += nums[i]\n",
    "            j = 0\n",
    "            while True:\n",
    "                # print(j, cd[j], s)\n",
    "                if cd[j] > s:\n",
    "                    break\n",
    "                elif cd[j] == s and i >= 1:\n",
    "                    return True\n",
    "                else:\n",
    "                    if s - cd[j] in md and i - xd[s-cd[j]] > 1:\n",
    "                        return True\n",
    "                    if j == len(cd) - 1:\n",
    "                        cd.append(cd[j]+k)\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "            if s in md:\n",
    "                md[s] += 1\n",
    "            else: \n",
    "                md[s] = 1\n",
    "                xd[s] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        sums=0\n",
    "        info={0:[]}\n",
    "        for i,num in enumerate(nums):\n",
    "            sums+=num\n",
    "            key=sums % k\n",
    "            if key in info:\n",
    "                info[key].append(i)\n",
    "            else:\n",
    "                info[key] = [i]\n",
    "            for j in info.get(key,[]):\n",
    "                if abs(i-j)>=2 or( key==0 and j>=1):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        length = len(nums)\n",
    "        # prefix_list = [0 for _ in range(length)]\n",
    "        prefix_sum_index_dict = defaultdict(list)\n",
    "        prefix_sum_index_dict[0].append(-1)\n",
    "\n",
    "        cur_sum = nums[0]%k\n",
    "        prefix_sum_index_dict[cur_sum].append(0)\n",
    "\n",
    "        for i in range(1,length):\n",
    "            cur_sum = (cur_sum+nums[i])%k\n",
    "            if prefix_sum_index_dict[cur_sum] and i-prefix_sum_index_dict[cur_sum][0]>=2:\n",
    "                return True\n",
    "            prefix_sum_index_dict[cur_sum].append(i)\n",
    "        \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        prefix_sum=dict()\n",
    "        prefix_sum[-1]=0\n",
    "        pref_sum=0\n",
    "        for i in range(len(nums)):\n",
    "            pref_sum+=nums[i]\n",
    "            prefix_sum[i]=pref_sum\n",
    "        '''\n",
    "        (n2*k+mod2)-(n1*k+mod1)=x\n",
    "        if mod2==mod1 --> x%k==0\n",
    "        '''\n",
    "\n",
    "        remainder2idx=dict()\n",
    "        remainder2idx[0]=-1\n",
    "        for idx,sum in prefix_sum.items():\n",
    "            remainder=sum%k\n",
    "            if remainder not in remainder2idx:\n",
    "                remainder2idx[remainder]=idx\n",
    "            else:\n",
    "                dist=idx-remainder2idx[remainder]\n",
    "                if dist>=2:\n",
    "                    return True\n",
    "                else:\n",
    "                    pass\n",
    "                    # dont need to update remainder2idx bc the far the better\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        prefix_sum=dict()\n",
    "        prefix_sum[-1]=0\n",
    "        pref_sum=0\n",
    "        for i in range(len(nums)):\n",
    "            pref_sum+=nums[i]\n",
    "            prefix_sum[i]=pref_sum\n",
    "        '''\n",
    "        (n2*k+mod2)-(n1*k+mod1)=x\n",
    "        if mod2==mod1 --> x%k==0\n",
    "        '''\n",
    "\n",
    "        remainder2idx=dict()\n",
    "        remainder2idx[0]=-1\n",
    "        for idx,sum in prefix_sum.items():\n",
    "            remainder=sum%k\n",
    "            if remainder not in remainder2idx:\n",
    "                remainder2idx[remainder]=idx\n",
    "            else:\n",
    "                dist=idx-remainder2idx[remainder]\n",
    "                if dist>=2:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        dic = defaultdict(list)\n",
    "        dp = [0 for _ in range(len(nums)+1)]\n",
    "\n",
    "        for i in range(1,len(nums)+1):\n",
    "            dp[i]=dp[i-1]+nums[i-1]\n",
    "        for i in range(len(nums)+1):\n",
    "            dp[i]=dp[i]%k\n",
    "        \n",
    "        for i in range(len(nums)+1):\n",
    "            dic[dp[i]].append(i)\n",
    "        for key in dic.keys():\n",
    "            if len(dic[key])>1:\n",
    "                if dic[key][-1]-dic[key][0]>1:return True\n",
    "        return False\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        prefix_sum = [0] * (len(nums) + 1)\n",
    "        remain = [0] * (len(nums) + 1)\n",
    "\n",
    "        for i in range(1, len(nums)+1):\n",
    "            # prefix_sum[i] = prefix_sum[i-1] + nums[i-1]\n",
    "            # remain[i] = prefix_sum[i] % k\n",
    "            remain[i] = (remain[i-1] + nums[i-1]) % k\n",
    "\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i, num in enumerate(remain):\n",
    "            dic[num].append(i)\n",
    "            if dic[num][-1] - dic[num][0] >= 2:\n",
    "                return True \n",
    "\n",
    "        # for i in range(len(nums) - 1):\n",
    "        #     if dic[remain[i]][-1] - i >= 2:\n",
    "        #         return True\n",
    "        return False \n",
    "\n",
    "        \n",
    "        # for i in range(len(nums)-1):\n",
    "        #     for j in range(i+2, len(nums)+1):\n",
    "        #         if j - i >= 2 and (prefix_sum[j] - prefix_sum[i]) % k == 0:\n",
    "        #             return True \n",
    "        # return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        cur_sum = 0\n",
    "        d = {}\n",
    "        d[0] = [-1]\n",
    "        for i in range(0, len(nums)):\n",
    "            cur_sum += nums[i]\n",
    "            if cur_sum%k not in d:\n",
    "                d[cur_sum%k] = [i]\n",
    "            else:\n",
    "                d[cur_sum%k].append(i)\n",
    "                if d[cur_sum%k][-1]-d[cur_sum%k][0]>=2:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        prefixSum_count, prefixSum = {0: [-1]}, 0  # Initialize with -1 to cover the case where a subarray starts from index 0\n",
    "        for i, num in enumerate(nums):\n",
    "            prefixSum += num\n",
    "            n = prefixSum % k\n",
    "            if n in prefixSum_count:\n",
    "                if i - prefixSum_count[n][-1] > 1:\n",
    "                    return True\n",
    "            else:\n",
    "                prefixSum_count[n] = [i]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: list[int], k: int) -> bool:\n",
    "        d1 = defaultdict(int)\n",
    "        d2 = defaultdict(int)\n",
    "        presum = nums[0]\n",
    "        t = presum % k\n",
    "        d1[t] += 1\n",
    "        d2[t] = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            presum += nums[i]\n",
    "            t = presum % k\n",
    "            if t == 0:\n",
    "                return True\n",
    "            if d1[t] == 1 and i - d2[t] >= 2:\n",
    "                return True\n",
    "            else:\n",
    "                if d1[t] == 0:\n",
    "                    d2[t] = i\n",
    "                    d1[t] = 1\n",
    "                else:\n",
    "                    pass\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        num=0\n",
    "        res=0\n",
    "        map={0:[-1]}\n",
    "        for i in range(len(nums)):\n",
    "            num+=nums[i]\n",
    "            tempList=map.get(num%k,[])\n",
    "            for j in tempList:\n",
    "                if i-j>=2:\n",
    "                    return True\n",
    "            map.setdefault(num%k,[])\n",
    "            map[num%k].append(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        dict=defaultdict(list)\n",
    "        total=0\n",
    "        dict[0].append(-1)\n",
    "\n",
    "        for i,j in enumerate(nums):\n",
    "            total += j\n",
    "            mod = total%k\n",
    "            \n",
    "            \n",
    "            if mod in dict  and i-dict[mod][0]>=2:\n",
    "                return True \n",
    "            dict[mod].append(i)\n",
    "            #print(dict)\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) == 1:  return False\n",
    "        sums = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            sums.append(sums[-1]+nums[i])\n",
    "        dic = {0:[-1]}\n",
    "        for i in range(len(sums)):\n",
    "            if sums[i] % k not in dic:  dic[sums[i]%k] = [i]\n",
    "            else:   dic[sums[i]%k].append(i)\n",
    "        print(dic)\n",
    "        for key, value in dic.items():\n",
    "            if (value[-1]-value[0]) >= 2:   return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        # x = list(accumulate(nums, initial=0))\n",
    "        d = defaultdict(list)\n",
    "        s = 0\n",
    "        d[0].append(0)\n",
    "        for i,v in enumerate(nums):\n",
    "            s += v\n",
    "            s %= k\n",
    "            d[s].append(i+1)\n",
    "            if d[s][-1] - d[s][0] >= 2:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        # 前缀和求余\n",
    "        remains=[]\n",
    "        summ=0\n",
    "        for num in nums:\n",
    "            summ=(summ+num)%k\n",
    "            remains.append(summ)\n",
    "        # 寻找remains中是否有0或者重复的元素\n",
    "        remain_dict=dict()\n",
    "        for i in range(len(remains)):\n",
    "            if remains[i] in remain_dict.keys():\n",
    "                remain_dict[remains[i]].append(i)\n",
    "            else:\n",
    "                remain_dict[remains[i]]=[i]\n",
    "        for key in remain_dict.keys():\n",
    "            if key==0:\n",
    "                if remain_dict[key][-1]>=1:\n",
    "                    return True\n",
    "            else:\n",
    "                if remain_dict[key][-1]-remain_dict[key][0]>1:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubarraySum(self, nums: List[int], k: int) -> bool:\n",
    "        dic=collections.defaultdict(list)\n",
    "        dic[0]=[-1]\n",
    "        presum=0\n",
    "        for i in range(len(nums)):\n",
    "            presum+=nums[i]\n",
    "            presum%=k\n",
    "            for j in dic[presum]:\n",
    "                if i-j>=2:\n",
    "                    return True\n",
    "            dic[presum].append(i)\n",
    "        return False\n",
    "                \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
